//
// Created by 高森森 on 2022/2/16.
//

#ifndef LEETCODE_SOLUTION50_H
#define LEETCODE_SOLUTION50_H
#include<iostream>
using namespace std;

#include <vector>

class Solution50 {
public:
    int trap(vector<int>& height) {
        if(height.size()<2){
            return 0;
        }
        int res=0;
        int n=height.size();
        vector<int>maxLeft(n);
        vector<int>maxRight(n);
        maxLeft[0]=0;
        maxRight[n-2]=0;
        for(int i=1;i<=n-2;i++){
            maxLeft[i]=max(maxLeft[i-1],height[i-1]);
        }
        for(int j=n-2;j>=1;j--)
        {
            maxRight[j]=max(maxRight[j+1],height[j+1]);
        }
        for(int i=1;i<=n-2;i++){
            int m=min(maxLeft[i],maxRight[i]);
            if(m>height[i]){
                res+=(m-height[i]);
            }
        }
        return res;
    }
    int trap2(vector<int>& height) {
        int sum=0;
        int n=height.size();
        int left=1;
        int right=n-2;
        int maxLeft=0;
        int maxRight=0;
        for(int i=1;i<=n-2;i++){
            //更新左指针
            if(height[left-1]<height[right+1]){
                maxLeft=max(maxLeft,height[left-1]);
                if(maxLeft>height[left])
                    sum+=maxLeft-height[left];
                left++;
            }
            //更新右指针
            else{
                maxRight=max(maxRight,height[right+1]);
                if(maxRight>height[right])
                    sum+=maxRight-height[right];
                right--;
            }
        }
        return sum;
    }
};


#endif //LEETCODE_SOLUTION50_H
